/*
 * @lc app=leetcode.cn id=208 lang=typescript
 *
 * [208] 实现 Trie (前缀树)
 */

// @lc code=start

// 节点
class TrieNode {
  // 当前节点为结尾是否成词
  isWord: boolean;
  // 下一个字符节点
  next: TrieNode[];
  constructor() {
    this.isWord = false;
    this.next = new Array(26).fill(null);
  }
}

class Trie {
  root: TrieNode;
  base: number;
  constructor() {
    this.root = new TrieNode();
    this.base = 'a'.charCodeAt(0);
  }

  insert(word: string): void {
    let node = this.root;
    const base = this.base;
    for (let char of word) {
      const idx = char.charCodeAt(0) - base;
      if (node.next[idx] === null) {
        node.next[idx] = new TrieNode();
      }
      node = node.next[idx];
    }
    node.isWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    const base = this.base;
    for (let char of word) {
      const idx = char.charCodeAt(0) - base;
      node = node.next[idx];
      if (node === null) return false;
    }
    return node.isWord;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    const base = this.base;
    for (let char of prefix) {
      const idx = char.charCodeAt(0) - base;
      node = node.next[idx];
      if (node === null) return false;
    }
    return true;
  }
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */
// @lc code=end
